package leetcode_600;

import java.util.Arrays;
import java.util.Random;

/**
 *@author 周杨
 *RandomPickWithWeight_528  带有权重的产生随机数
 *describe:用binarysearch 搜索区间 AC 8%
 *2018年9月11日 上午10:20:53
 */
public class RandomPickWithWeight_528 {
	public static void main(String[] args) {
		RandomPickWithWeight_528 test=new RandomPickWithWeight_528(new int [] {1,3,2});
		System.out.println(test.pickIndex());
	}
	
	 int total;
	 int [] w;
	 Random rd;
	 public RandomPickWithWeight_528(int[] w) {
	       this.total=0;
	       for(int i=0;i<w.length;++i) {
	    	   total+=w[i];
	    	   w[i]=total;
	       }
	       this.w=w;
	       this.rd=new Random();
	 }
	    
	 public int pickIndex() {
	       int num=rd.nextInt(this.total)+1;
	       int index=Arrays.binarySearch(this.w, num);
	       if(index>=0)
	    	   return index;
	       return -(index+1);
	 }
}
